home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / irit / bool1low.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  36.0 KB  |  1,056 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d (not only polygonal) solid modeller.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the low level boolean operations. The routines in this  *
  7. * module should be accessed from "bool-hi.c" module only.             *
  8. *   Note the polygons of the two given objects may not be convex, and must   *
  9. * be subdivided into convex ones in the boolean upper level routines (module *
  10. * bool-hi.c). All the routines of this module expects objects with convex    *
  11. * polygons only although they might return objects with non convex polygons, *
  12. * but marked as so (via polygons CONVEX tags - see IPPolygonStruct def.)!    *
  13. *   Because Bool-low.c module was too big, it was subdivided to two:         *
  14. * Bool1Low.c - mainly handles the intersection polyline between the oper.    *
  15. * Bool2Low.c - mainly handles the polygon extraction from operands given the *
  16. *           polyline of intersection and the adjacencies (see ADJACNCY.C) *
  17. * Note we said mainly has routines CAN call one another!             *
  18. *****************************************************************************/
  19.  
  20. /* #define DEBUG2             If defined, defines some printing routines. */
  21. /* #define DEBUG3             Print messages to entry/exit from routines. */
  22.  
  23. #include <stdio.h>
  24. #include <ctype.h>
  25. #include <math.h>
  26. #include <string.h>
  27. #include "program.h"
  28. #include "adjacncy.h"
  29. #include "allocate.h"
  30. #include "booleang.h"
  31. #include "booleanl.h"
  32. #include "geomat3d.h"
  33. #include "objects.h"
  34. #include "windows.h"
  35.  
  36. static int ObjectsIntersect, GlblPolySortAxis, GlblHandleCoplanar;
  37.  
  38. static IPObjectStruct *BooleanLowGenInOut(IPObjectStruct *PObj1, int InOut);
  39. static void SetHandleCoplanarAndPolySort(void);
  40. static void BooleanLowInterAll(IPObjectStruct *PObj1, IPObjectStruct *PObj2);
  41. static void BooleanLowInterOne(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2);
  42. static InterSegmentStruct *InterSegmentPoly(IPPolygonStruct *Pl,
  43.                 IPPolygonStruct *SegPl, PointType Segment[2]);
  44. static void SwapPointInterList(InterSegmentStruct *PSeg);
  45. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  46.                         InterSegmentStruct **PSegList);
  47. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  48.                         InterSegmentStruct **PSegList);
  49. static void SortOpenReverseLoop(SortOpenStruct *PSHead);
  50. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  51.        SortOpenStruct *PSTemp, PointType Pt, IPVertexStruct *V,
  52.                             IPPolygonStruct *Pl);
  53. static IPObjectStruct *PolylineFromInterSeg(IPObjectStruct *PObj);
  54. #if defined(ultrix) && defined(mips)
  55. static int BooleanPrepObjectCmpr(VoidPtr VPoly1, VoidPtr VPoly2);
  56. #else
  57. static int BooleanPrepObjectCmpr(const VoidPtr VPoly1, const VoidPtr VPoly2);
  58. #endif /* ultrix && mips (no const support) */
  59. static void BooleanPrepObject(IPObjectStruct *PObj);
  60.  
  61. #ifdef DEBUG2
  62. static void PrintVrtxList(IPVertexStruct *V);
  63. static void PrintInterList(InterSegmentStruct *PInt);
  64. #endif /* DEBUG2 */
  65.  
  66. /*****************************************************************************
  67. *   Routine to find the part of PObj1 which is out of PObj2:             *
  68. *****************************************************************************/
  69. IPObjectStruct *BooleanLow1Out2(IPObjectStruct *PObj1, IPObjectStruct *PObj2)
  70. {
  71. #ifdef DEBUG3
  72.     printf("Enter BooleanLow1Out2\n");
  73. #endif /* DEBUG3 */
  74.  
  75.     GenAdjacencies(PObj1);
  76.  
  77.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  78.     ObjectsIntersect = FALSE;
  79.     BooleanLowInterAll(PObj1, PObj2);
  80.  
  81.     /* Generate all the polygons in PObj1 which are out of PObj2. */
  82.     if (!ObjectsIntersect) {
  83.     FatalBooleanError(FTL_BOOL_NO_INTER);
  84.     }
  85.  
  86.     return BooleanLowGenInOut(PObj1, FALSE);
  87. }
  88.  
  89. /*****************************************************************************
  90. *   Routine to find the part of PObj1 which is in PObj2:             *
  91. *****************************************************************************/
  92. IPObjectStruct *BooleanLow1In2(IPObjectStruct *PObj1, IPObjectStruct *PObj2)
  93. {
  94. #ifdef DEBUG3
  95.     printf("Enter BooleanLow1In2\n");
  96. #endif /* DEBUG3 */
  97.  
  98.     GenAdjacencies(PObj1);
  99.  
  100.     /* Find all intersections of PObj1 polygons with PObj2 polygons. */
  101.     ObjectsIntersect = FALSE;
  102.     BooleanLowInterAll(PObj1, PObj2);
  103.  
  104.     /* Generate all the polygons in PObj1 which are in PObj2. */
  105.     if (!ObjectsIntersect) {
  106.     FatalBooleanError(FTL_BOOL_NO_INTER);
  107.     }
  108.     return BooleanLowGenInOut(PObj1, TRUE);
  109. }
  110.  
  111. /*****************************************************************************
  112. *   Scan the InterSegmentList of each polygon and decide using Intersection  *
  113. * list, if it is IN relative to the other object. Note that for polygons     *
  114. * that does not intersect at all, we use the polygon adjacencies to decide   *
  115. * if they are IN or not.                             *
  116. *****************************************************************************/
  117. static IPObjectStruct *BooleanLowGenInOut(IPObjectStruct *PObj, int InOut)
  118. {
  119.     if (BooleanOutputInterCurve) {
  120.     /* Return a polyline object - extract the InterSegment list of each  */
  121.     /* polygon into open/closed polyline loops object.             */
  122.     return PolylineFromInterSeg(PObj);
  123.     }
  124.     else {
  125.     if (GlblHandleCoplanar) {
  126.         IPObjectStruct
  127.         *PObjNew = ExtractPolygons(PObj, InOut);
  128.         IPPolygonStruct
  129.         *Pl = PObjNew -> U.Pl;
  130.  
  131.         /* Purge all polygons that were tagged being coplanar. */
  132.         while (Pl != NULL && IS_COPLANAR_POLY(Pl)) {
  133.             PObjNew -> U.Pl = PObjNew -> U.Pl -> Pnext;
  134.             IPFreePolygon(Pl);
  135.         Pl = PObjNew -> U.Pl;
  136.         }
  137.         if (Pl != NULL) {
  138.         while (Pl -> Pnext != NULL) {
  139.             if (IS_COPLANAR_POLY(Pl -> Pnext)) {
  140.             IPPolygonStruct
  141.                 *PlTemp = Pl -> Pnext;
  142.  
  143.             Pl -> Pnext = PlTemp -> Pnext;
  144.             IPFreePolygon(PlTemp);
  145.                 }
  146.                 else
  147.                 Pl = Pl -> Pnext;
  148.         }
  149.         }
  150.  
  151.         return PObjNew;
  152.     }
  153.     else
  154.         return ExtractPolygons(PObj, InOut);
  155.     }
  156. }
  157.  
  158. /*****************************************************************************
  159. *   Create a polyline object out of the intersection list of the polygons.   *
  160. *****************************************************************************/
  161. static IPObjectStruct *PolylineFromInterSeg(IPObjectStruct *PObj)
  162. {
  163.     IPObjectStruct *PObjRet;
  164.     IPPolygonStruct *PlTemp, *PlObj,
  165.     *PlHead = NULL;
  166.     InterSegmentStruct *PInter, *PInterNext;
  167.     InterSegListStruct *PClosed, *POpen, *PClosedNext, *POpenNext;
  168.     IPVertexStruct *V;
  169.  
  170.     PlObj = PObj -> U.Pl;
  171.     while (PlObj != NULL) {
  172.     LoopsFromInterList(PlObj, &PClosed, &POpen);
  173.     while (POpen != NULL) {
  174.         /* Make one polyline from each loop in list: */
  175.         PInter = POpen -> PISeg;
  176.         POpenNext = POpen -> Pnext;
  177.  
  178.         PlTemp = IPAllocPolygon(0, 0, NULL, NULL);
  179.         PlTemp -> PVertex = V = IPAllocVertex(0, 0, NULL, NULL);
  180.         PT_COPY(V -> Coord, PInter -> PtSeg[0]);
  181.         while (PInter) {
  182.         PInterNext = PInter -> Pnext;
  183.  
  184.         V -> Pnext = IPAllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  185.         PT_COPY(V -> Coord, PInter -> PtSeg[1]);
  186.  
  187.         IritFree((VoidPtr) PInter);
  188.         PInter = PInterNext;
  189.         }
  190.         PlTemp -> Pnext = PlHead;
  191.         PlHead = PlTemp;
  192.  
  193.         IritFree((VoidPtr) POpen);
  194.         POpen = POpenNext;
  195.     }
  196.     while (PClosed != NULL) {
  197.         /* Make one polyline from each loop in list: */
  198.         PInter = PClosed -> PISeg;
  199.         PClosedNext = PClosed -> Pnext;
  200.  
  201.         PlTemp = IPAllocPolygon(0, 0, NULL, NULL);
  202.         PlTemp -> PVertex = V = IPAllocVertex(0, 0, NULL, NULL);
  203.         PT_COPY(V -> Coord, PInter -> PtSeg[0]);
  204.         while (PInter) {
  205.         V -> Pnext = IPAllocVertex(0, 0, NULL, NULL); V = V -> Pnext;
  206.         PT_COPY(V -> Coord, PInter -> PtSeg[1]);
  207.         PInter = PInter -> Pnext;
  208.         }
  209.         PlTemp -> Pnext = PlHead;
  210.         PlHead = PlTemp;
  211.  
  212.         IritFree((VoidPtr) PClosed);
  213.         PClosed = PClosedNext;
  214.     }
  215.     PlObj = PlObj -> Pnext;
  216.     }
  217.  
  218.     PObjRet = GenPolyObject("", PlHead, NULL);
  219.     IP_SET_POLYLINE_OBJ(PObjRet);        /* Mark it as polyline object. */
  220.     return PObjRet;
  221. }
  222.  
  223. /*****************************************************************************
  224. *   Routine to compute BBox for all polygons in provided object PObj. Also,  *
  225. * the polygons are sorted in the list with according to thier minimal BBox   *
  226. * value in GlblPolySortAxis axis.                         *
  227. *****************************************************************************/
  228. #if defined(ultrix) && defined(mips)
  229. static int BooleanPrepObjectCmpr(VoidPtr VPoly1, VoidPtr VPoly2)
  230. #else
  231. static int BooleanPrepObjectCmpr(const VoidPtr VPoly1, const VoidPtr VPoly2)
  232. #endif /* ultrix && mips (no const support) */
  233. {
  234.     RealType
  235.     Diff = (*((IPPolygonStruct **) VPoly1)) -> BBox[0][GlblPolySortAxis] -
  236.            (*((IPPolygonStruct **) VPoly2)) -> BBox[0][GlblPolySortAxis];
  237.  
  238.     return SIGN(Diff);
  239. }
  240.  
  241. /*****************************************************************************
  242. *   Routine to compute BBox for all polygons in provided object PObj. Also,  *
  243. * the polygons are sorted in the list with according to their minimal BBox   *
  244. * value in GlblPolySortAxis axis.                         *
  245. *****************************************************************************/
  246. static void BooleanPrepObject(IPObjectStruct *PObj)
  247. {
  248.     int i,
  249.     PolyCount = 0;
  250.     IPPolygonStruct **PlArray, **PlTemp,
  251.     *Pl = PObj -> U.Pl;
  252.  
  253.     /* Count how many polygons this object have and make sure all have bbox. */
  254.     while (Pl != NULL)
  255.     {
  256.     PolyCount++;
  257.  
  258.     if (GlblHandleCoplanar)
  259.         RST_COPLANAR_POLY(Pl);
  260.  
  261.     if (!IP_HAS_BBOX_POLY(Pl)) {              /* Compute it now. */
  262.         RealType
  263.         *BBoxMin = Pl -> BBox[0],
  264.         *BBoxMax = Pl -> BBox[1];
  265.         IPVertexStruct
  266.         *V = Pl -> PVertex;
  267.  
  268.         BBoxMin[0] = BBoxMin[1] = BBoxMin[2] = INFINITY;
  269.         BBoxMax[0] = BBoxMax[1] = BBoxMax[2] = -INFINITY;
  270.  
  271.         do {
  272.             for (i = 0; i < 3; i++) {
  273.                 if (BBoxMin[i] > V -> Coord[i])
  274.             BBoxMin[i] = V -> Coord[i];
  275.                 if (BBoxMax[i] < V -> Coord[i])
  276.             BBoxMax[i] = V -> Coord[i];
  277.             }
  278.  
  279.         V = V -> Pnext;
  280.         }
  281.         while (V != NULL && V != Pl -> PVertex);
  282.  
  283.         IP_SET_BBOX_POLY(Pl);
  284.     }
  285.         
  286.         Pl = Pl -> Pnext;
  287.     }
  288.  
  289.     /* Sort the polygons with according to minimal BBox in GlblPolySortAxis. */
  290.     PlArray = (IPPolygonStruct **) IritMalloc(sizeof(IPPolygonStruct *) *
  291.                             PolyCount);
  292.     for (Pl = PObj -> U.Pl, PlTemp = PlArray; Pl != NULL; Pl = Pl -> Pnext)
  293.     *PlTemp++ = Pl;
  294.  
  295.     qsort(PlArray, PolyCount, sizeof(IPPolygonStruct *), BooleanPrepObjectCmpr);
  296.  
  297.     for (i = 1; i < PolyCount; i++)
  298.     PlArray[i - 1] -> Pnext = PlArray[i];
  299.     PlArray[PolyCount - 1] -> Pnext = NULL;
  300.     PObj -> U.Pl = PlArray[0];
  301.     IritFree((VoidPtr) PlArray);
  302. }
  303.  
  304. /*****************************************************************************
  305. *  Routine to set GlblPolySortAxis according to "POLYSORT" object and set    *
  306. * GlblHandleCoplanar according to "COPLANAR" object.                 *
  307. *****************************************************************************/
  308. static void SetHandleCoplanarAndPolySort(void)
  309. {
  310.     IPObjectStruct
  311.     *PObj1 = GetObject("POLYSORT"),
  312.     *PObj2 = GetObject("COPLANAR");
  313.  
  314.     if (PObj1 == NULL || !IP_IS_NUM_OBJ(PObj1)) {
  315.     WndwInputWindowPutStr("No numeric object name POLYSORT is defined");
  316.     GlblPolySortAxis = 0;
  317.     }
  318.     else {
  319.     GlblPolySortAxis = (int) (PObj1 -> U.R);
  320.     if (GlblPolySortAxis > 2 || GlblPolySortAxis < 0)
  321.         GlblPolySortAxis = 0;
  322.     }
  323.  
  324.     if (PObj2 == NULL || !IP_IS_NUM_OBJ(PObj2)) {
  325.     WndwInputWindowPutStr("No numeric object name COPLANAR is defined");
  326.     GlblHandleCoplanar = FALSE;
  327.     }
  328.     else
  329.     GlblHandleCoplanar = (int) (PObj2 -> U.R);
  330. }
  331.  
  332. /*****************************************************************************
  333. *   Routine to find all the intersections between all PObj1 polygons with    *
  334. * PObj2 polygons. The intersections are saved as a list of segments (struct  *
  335. * InterSegmentStruct) in each of PObj1 polygons using the PAux pointer (see  *
  336. * IPPolygonStruct). Note PObj2 is not modified at all, and in PObj1, only    *
  337. * PAux of each polygon is set to the segment list, or NULL if none.         *
  338. *****************************************************************************/
  339. static void BooleanLowInterAll(IPObjectStruct *PObj1, IPObjectStruct *PObj2)
  340. {
  341.     IPPolygonStruct *Pl1, *Pl2, *Pl2Start;
  342.  
  343. #ifdef DEBUG3
  344.     printf("Enter BooleanLowInterAll\n");
  345. #endif /* DEBUG3 */
  346.  
  347.     SetHandleCoplanarAndPolySort();
  348.  
  349.     /* Sort polygons and compute BBox for them if none exists. */
  350.     BooleanPrepObject(PObj1);
  351.     BooleanPrepObject(PObj2);
  352.     Pl2Start = PObj2 -> U.Pl;
  353.     
  354.     Pl1 = PObj1 -> U.Pl;
  355.     while (Pl1 != NULL) {
  356.     Pl1 -> PAux = NULL;       /* Empty InterSegment list to start with: */
  357.  
  358.     /* Intersect Pl1 against the Pl2 list until end of Pl2 list or       */
  359.     /* until the minimum of Pl2 polygon is larger than Pl1 maximum.      */
  360.     Pl2 = Pl2Start;
  361.     while (Pl2 != NULL &&
  362.            Pl1 -> BBox[1][GlblPolySortAxis] >=
  363.                     Pl2 -> BBox[0][GlblPolySortAxis]) {
  364.         if (Pl1 -> BBox[1][0] < Pl2 -> BBox[0][0] ||
  365.         Pl1 -> BBox[1][1] < Pl2 -> BBox[0][1] ||
  366.         Pl1 -> BBox[1][2] < Pl2 -> BBox[0][2] ||
  367.         Pl2 -> BBox[1][0] < Pl1 -> BBox[0][0] ||
  368.         Pl2 -> BBox[1][1] < Pl1 -> BBox[0][1] ||
  369.         Pl2 -> BBox[1][2] < Pl1 -> BBox[0][2]) {
  370.         /* The Bounding boxes do not intersect, skip polygons. */
  371.         }
  372.         else
  373.         BooleanLowInterOne(Pl1, Pl2);
  374.  
  375.         /* If Pl2 maximum is smaller than Pl1 minimum there is no reason */
  376.         /* to consider this Pl2 polygon any more as it cannot intersect  */
  377.         /* any more polygons in the Pl1 list.                            */
  378.         if (Pl2 -> BBox[1][GlblPolySortAxis] <
  379.                           Pl2 -> BBox[1][GlblPolySortAxis] &&
  380.         Pl2Start == Pl2)
  381.         Pl2Start = Pl2 -> Pnext;
  382.                                                         
  383.         Pl2 = Pl2 -> Pnext;
  384.     }
  385.  
  386.     if (Pl1 -> PAux != NULL)             /* If any intersection. */
  387.         ObjectsIntersect = TRUE;
  388.  
  389.     Pl1 = Pl1 -> Pnext;
  390.     }
  391.  
  392. #ifdef DEBUG3
  393.     printf("Exit BooleanLowInterAll\n");
  394. #endif /* DEBUG3 */
  395. }
  396.  
  397. /*****************************************************************************
  398. *   Routine to intersect polygon Pl1, with polygon Pl2. If found common      *
  399. * intersection, that segment will be added to the InterSegmentStruct list    *
  400. * saved in Pl1 PAux list.                             *
  401. *   Note that as the two polygons convex, only one segment can result from   *
  402. * such intersection.                                 *
  403. *   Algorithm: intersect all Pl2 edges with Pl1 plane. If found that         *
  404. * (exactly) two vertices (one segment) of Pl2 do intersect Pl1 plane then:   *
  405. * Perform clipping of the segment against Pl1. If result is not empty, add   *
  406. * the result segment to Pl1 InterSegmentStruct list (saved at PAux of         *
  407. * polygon - see IPPolygonStruct).                         *
  408. *****************************************************************************/
  409. static void BooleanLowInterOne(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2)
  410. {
  411.     int NumOfInter = 0;
  412.     RealType TInter[2],
  413.     *Plane1 = Pl1 -> Plane,                   /* For faster access. */
  414.     *Plane2 = Pl2 -> Plane;
  415.     PointType Inter[2], Dir;
  416.     IPVertexStruct *Vnext,
  417.     *V = Pl2 -> PVertex;
  418.     InterSegmentStruct *PSeg, *PLSeg;
  419.  
  420. #ifdef DEBUG3
  421.     printf("Enter BooleanLowInterOne\n");
  422. #endif /* DEBUG3 */
  423.  
  424.     if ((APX_EQ(Plane1[0], Plane2[0]) &&
  425.      APX_EQ(Plane1[1], Plane2[1]) &&
  426.      APX_EQ(Plane1[2], Plane2[2]) &&
  427.      APX_EQ(Plane1[3], Plane2[3])) ||
  428.     (APX_EQ(Plane1[0], -Plane2[0]) &&
  429.      APX_EQ(Plane1[1], -Plane2[1]) &&
  430.      APX_EQ(Plane1[2], -Plane2[2]) &&
  431.      APX_EQ(Plane1[3], -Plane2[3]))) {
  432.     /* The two polygons are coplanar, do not attempt to intersect. */
  433.     if (GlblHandleCoplanar) {
  434.         SET_COPLANAR_POLY(Pl1);
  435.         SET_COPLANAR_POLY(Pl2);
  436.     }
  437.     else {
  438.         WndwInputWindowPutStr("Boolean: coplanar polygons detected. Enable COPLANAR variable.");
  439.     }
  440.     }
  441.     else {
  442.     do {
  443.         Vnext = V -> Pnext;
  444.         PT_SUB(Dir, Vnext -> Coord, V -> Coord);
  445.         if (CGPointFromLinePlane01(V -> Coord, Dir, Plane1,
  446.                  Inter[NumOfInter], &TInter[NumOfInter]) &&
  447.             ((NumOfInter == 0) || (NumOfInter == 1 &&
  448.                        !PT_APX_EQ(Inter[0], Inter[1]))))
  449.             NumOfInter++;
  450.         if (NumOfInter == 2)
  451.         break;               /* Cannt have more intersections. */
  452.  
  453.         V = Vnext;
  454.     }
  455.     while (V != NULL && V != Pl2 -> PVertex);
  456.     }
  457.  
  458.     switch (NumOfInter) {
  459.     case 0:
  460.         break;
  461.     case 1:
  462.         /* One intersection is possible if only one vertex of Pl2 is in  */
  463.         /* the plane of Pl1, all other vertices are on one side of plane.*/
  464.         break;
  465.     case 2:
  466.         /* Clip the segment against the polygon and insert if not empty: */
  467.         if ((PSeg = InterSegmentPoly(Pl1, Pl2, Inter)) != NULL) {
  468.         /* insert that segment to list of Pl1. Note however that the */
  469.         /* intersection may be exactly on 2 other polygons boundary, */
  470.         /* And therefore creates the same intersection edge TWICE!   */
  471.         /* Another possiblity is on same case, the other polygon     */
  472.         /* will have that inter. edge on its edge, and its ignored.  */
  473.         /* We therefore test for duplicates and ignore edge if so    */
  474.         if (PSeg -> V[0] != NULL && PSeg -> V[0] == PSeg -> V[1]) {
  475.             IritFree((VoidPtr) PSeg);               /* Ignore it! */
  476.             return;
  477.         }
  478.         PLSeg = (InterSegmentStruct *) Pl1 -> PAux;
  479.         while (PLSeg != NULL) {
  480.             if ((PT_APX_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[0]) &&
  481.              PT_APX_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[1])) ||
  482.             (PT_APX_EQ(PSeg -> PtSeg[0], PLSeg -> PtSeg[1]) &&
  483.              PT_APX_EQ(PSeg -> PtSeg[1], PLSeg -> PtSeg[0]))) {
  484.             IritFree((VoidPtr) PSeg);           /* Ignore it! */
  485.             return;
  486.             }
  487.             PLSeg = PLSeg -> Pnext;
  488.         }
  489.  
  490.         PSeg -> Pnext = (InterSegmentStruct *) Pl1 -> PAux;
  491.         Pl1 -> PAux = (VoidPtr) PSeg;
  492.         }
  493.         break;
  494.     }
  495.  
  496. #ifdef DEBUG3
  497.     printf("Exit BooleanLowInterOne\n");
  498. #endif /* DEBUG3 */
  499. }
  500.  
  501. /*****************************************************************************
  502. *   Intersects the given segment (given as two end points), with the given   *
  503. * polygon (which must be convex). Upto two intersections are possible, as    *
  504. * again, the polygon is convex. Note Segment polygon is given as SegPl.      *
  505. *****************************************************************************/
  506. static InterSegmentStruct *InterSegmentPoly(IPPolygonStruct *Pl,
  507.                 IPPolygonStruct *SegPl, PointType Segment[2])
  508. {
  509.     int i, Reverse, Res,
  510.     NumOfInter = 0;
  511.     RealType TInter[3], temp, Min, Max, *PtSeg0, *PtSeg1;
  512.     PointType Dir, Inter[2], SegDir, Pt1, Pt2;
  513.     IPVertexStruct *VInter[2], *Vnext,
  514.     *V = Pl -> PVertex;
  515.     InterSegmentStruct *PSeg;
  516.  
  517.     /* Find the segment direction vector: */
  518.     PT_SUB(SegDir, Segment[1], Segment[0]);
  519.  
  520. #ifdef DEBUG3
  521.     printf("Enter InterSegmentPoly\n");
  522. #endif /* DEBUG3 */
  523.  
  524.     do {
  525.     Vnext = V -> Pnext;
  526.     PT_SUB(Dir, Vnext -> Coord, V -> Coord);
  527.     /* Find the intersection of the segment with all the polygon edges: */
  528.     /* Note the t parameter value of the edge (temp) must be in [0..1]. */
  529.     if ((Res = CG2PointsFromLineLine(Segment[0], SegDir,
  530.         V -> Coord, Dir, Pt1, &TInter[NumOfInter], Pt2, &temp)) != 0 &&
  531.         (temp > 0.0 || APX_EQ(temp, 0.0)) &&
  532.         (temp < 1.0 || APX_EQ(temp, 1.0)) && PT_APX_EQ(Pt1, Pt2) &&
  533.         (NumOfInter == 0 ||
  534.          (NumOfInter == 1 && !APX_EQ(TInter[0], TInter[1])))) {
  535.         PT_COPY(Inter[NumOfInter], Pt1);
  536.         VInter[NumOfInter++] = V;/* Save pointer to intersected edge. */
  537.     }
  538.     else {
  539.         /* If Res == 0 its parallel to edge. If distance is zero then    */
  540.         /* line is on the edge line itself - quit from this one!         */
  541.         if (!Res && CGDistPointLine(Segment[0], V -> Coord, Dir) <
  542.                                 EPSILON) {
  543.         /* Wipe out adjacency of this vertex as we dont want to      */
  544.         /* propagate through this one nothing - its on in/out border.*/
  545.         IPVertexStruct *Vtemp;
  546.  
  547.         if (V -> PAdj == NULL)
  548.             return NULL;
  549.  
  550.         Vtemp = V -> PAdj -> PVertex;
  551.         do {/* Find the edge on the other polygon to wipe out first. */
  552.             if (Vtemp -> PAdj == Pl) {
  553.             Vtemp -> PAdj = NULL;
  554.             break;
  555.             }
  556.             Vtemp = Vtemp -> Pnext;
  557.         }
  558.         while (Vtemp != NULL && Vtemp != V -> PAdj -> PVertex);
  559.         V -> PAdj = NULL;        /* And wipe out ours also... */
  560.         return NULL;
  561.         }
  562.     }
  563.  
  564.     V = Vnext;
  565.     }
  566.     while (V != NULL && V != Pl -> PVertex);
  567.  
  568.     switch (NumOfInter) {
  569.     case 0:
  570.         return NULL;
  571.     case 1:
  572.         /* One intersection is possible if segment intersects one vertex */
  573.         /* of polygon and all other vertices are on same side of segment.*/
  574.         return NULL;
  575.     case 2:
  576.         /* In order the segment to really intersect the polygon, it must */
  577.         /* at list part of t in [0..1] in the polygon. Test it:         */
  578.         Min = MIN(TInter[0], TInter[1]);
  579.         Max = MAX(TInter[0], TInter[1]);
  580.         Reverse = TInter[0] > TInter[1];
  581.         if (Min >= 1.0 || APX_EQ(Min, 1.0) ||
  582.         Max <= 0.0 || APX_EQ(Max, 0.0))
  583.         return NULL;
  584.  
  585.         PSeg = (InterSegmentStruct *)
  586.         IritMalloc(sizeof(InterSegmentStruct));
  587.         PSeg -> Pl = SegPl;     /* Pointer to other (intersect) polygon. */
  588.  
  589.         /* Handle the Min end point: */
  590.         if (APX_EQ(Min, 0.0)) {
  591.         PtSeg0 = Segment[0];
  592.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  593.         }
  594.         else if (Min < 0.0) {
  595.         PtSeg0 = Segment[0];
  596.         PSeg -> V[0] = NULL;             /* End is internal. */
  597.         }
  598.         else { /* Min > 0.0 */
  599.         PtSeg0 = (Reverse ? Inter[1] : Inter[0]);
  600.         PSeg -> V[0] = (Reverse ? VInter[1] : VInter[0]);
  601.         }
  602.  
  603.         /* Handle the Max end point: */
  604.         if (APX_EQ(Max, 1.0)) {
  605.         PtSeg1 = Segment[1];
  606.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  607.         }
  608.         else if (Max > 1.0) {
  609.         PtSeg1 = Segment[1];
  610.         PSeg -> V[1] = NULL;             /* End is internal. */
  611.         }
  612.         else { /* Max < 1.0 */
  613.         PtSeg1 = (Reverse ? Inter[0] : Inter[1]);
  614.         PSeg -> V[1] = (Reverse ? VInter[0] : VInter[1]);
  615.         }
  616.  
  617.         PT_COPY(PSeg -> PtSeg[0], PtSeg0); /* The two segment end point. */
  618.             PT_COPY(PSeg -> PtSeg[1], PtSeg1);
  619.  
  620.         for (i = 0; i < 3; i++) {         /* Make zeros look nicer... */
  621.         if (ABS(PSeg -> PtSeg[0][i]) < EPSILON)
  622.             PSeg -> PtSeg[0][i] = 0.0;
  623.         if (ABS(PSeg -> PtSeg[1][i]) < EPSILON)
  624.             PSeg -> PtSeg[1][i] = 0.0;
  625.         }
  626.         if (PT_APX_EQ(PSeg -> PtSeg[0], PSeg -> PtSeg[1])) {
  627.         IritFree((VoidPtr) PSeg);
  628.         return NULL;
  629.         }
  630.         return PSeg;
  631.     }
  632.     return NULL;                    /* Makes warning silent. */
  633. }
  634.  
  635. /*****************************************************************************
  636. *   Given a polygon with the intersection list, create the polylines loop(s) *
  637. * out of it, which can be one of the two:                     *
  638. * 1. Closed loop - all the intersection create a loop in one polygon.         *
  639. * 2. Open polyline - if the intersection crosses the polygon boundary. In    *
  640. *    this case the two end point of the polyline, must lay on polygon         *
  641. *    boundary.                                     *
  642. * In both cases, the polyline will be as follows:                 *
  643. * First point at first list element at PtSeg[0] (see InterSegmentStruct).    *
  644. * Second point at first list element at PtSeg[1] (see InterSegmentStruct).   *
  645. * Point i at list element (i-1) at PtSeg[0] (PtSeg[1] is not used!).         *
  646. * In the closed loop case the last point is equal to first.             *
  647. * Both cases returns NULL terminated list.                     *
  648. *****************************************************************************/
  649. void LoopsFromInterList(IPPolygonStruct *Pl,
  650.         InterSegListStruct **PClosed, InterSegListStruct **POpen)
  651. {
  652.     InterSegmentStruct *PSeg, *PSegHead, *PSegTemp, *PSegNewTemp;
  653.     InterSegListStruct *PSLTemp;
  654.  
  655. #ifdef DEBUG3
  656.     printf("Enter LoopsFromInterList\n");
  657. #endif /* DEBUG3 */
  658.  
  659.     *PClosed = (*POpen) = NULL;
  660.  
  661.     if ((PSeg = (InterSegmentStruct *) Pl -> PAux) == NULL) {
  662.     return;
  663.     }
  664.     else {
  665.     /* Do intersect - find if there are closed loops and/or open ones:   */
  666.     Pl -> PAux = NULL;
  667.     while (TRUE) {
  668.         /* First, we look for open loops - scans linearly (maybe should  */
  669.         /* be done more efficiently) for segment on boundary and start   */
  670.         /* build chain from it (up to the other end, on the boundary).   */
  671.         PSegHead = PSeg;
  672.         while (PSegHead) {
  673.         if (PSegHead -> V[0] != NULL || PSegHead -> V[1] != NULL) {
  674.             /* Found one - make it in correct order, del. from list: */
  675.             if (PSegHead -> V[0] == NULL) SwapPointInterList(PSegHead);
  676.             DeleteSegInterList(PSegHead, &PSeg);
  677.             break;
  678.         }
  679.         else
  680.             PSegHead = PSegHead -> Pnext;
  681.         }
  682.         if (PSegHead == NULL)
  683.         break;                /* No more open segments here... */
  684.  
  685.         PSegTemp = PSegHead;
  686.         while (PSegTemp -> V[1] == NULL) {
  687.         /* Search for matching to the second boundary end: */
  688.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  689.         PSegTemp -> Pnext = PSegNewTemp;
  690.         PSegTemp = PSegNewTemp;
  691.         }
  692.         PSegTemp -> Pnext = NULL;
  693.         PSLTemp = (InterSegListStruct *)
  694.         IritMalloc(sizeof(InterSegListStruct));
  695.         PSLTemp -> PISeg = PSegHead;
  696.         PSLTemp -> Pnext = (*POpen);
  697.         *POpen = PSLTemp;
  698.     }
  699.  
  700.     while (TRUE) {
  701.         /* Now, we look for closed loops - pick one segment and search   */
  702.         /* for matching until you close the loop.                 */
  703.         PSegHead = PSeg;
  704.         if (PSegHead == NULL)
  705.         break;              /* No more closed segments here... */
  706.         DeleteSegInterList(PSegHead, &PSeg);
  707.  
  708.         PSegTemp = PSegHead;
  709.         while (!PT_APX_EQ(PSegTemp -> PtSeg[1], PSegHead -> PtSeg[0])) {
  710.         /* Search for matching until we back at first point: */
  711.         PSegNewTemp = FindMatchInterList(PSegTemp -> PtSeg[1], &PSeg);
  712.         PSegTemp -> Pnext = PSegNewTemp;
  713.         PSegTemp = PSegNewTemp;
  714.         }
  715.         PSegTemp -> Pnext = NULL;
  716.         PSLTemp = (InterSegListStruct *)
  717.         IritMalloc(sizeof(InterSegListStruct));
  718.         PSLTemp -> PISeg = PSegHead;
  719.         PSLTemp -> Pnext = (*PClosed);
  720.         *PClosed = PSLTemp;
  721.     }
  722.     }
  723.  
  724. #ifdef DEBUG3
  725.     printf("Exit LoopsFromInterList\n");
  726. #endif /* DEBUG3 */
  727. }
  728.  
  729. /*****************************************************************************
  730. * Swap the two points in the InterSegmentStruct (modifies PtSeg & V entries) *
  731. *****************************************************************************/
  732. static void SwapPointInterList(InterSegmentStruct *PSeg)
  733. {
  734.     PointType Pt;
  735.     IPVertexStruct *V;
  736.  
  737.     PT_COPY(Pt,              PSeg -> PtSeg[0]);
  738.     PT_COPY(PSeg -> PtSeg[0], PSeg -> PtSeg[1]);
  739.     PT_COPY(PSeg -> PtSeg[1], Pt);
  740.  
  741.     V         = PSeg -> V[0];
  742.     PSeg -> V[0] = PSeg -> V[1];
  743.     PSeg -> V[1] = V;
  744. }
  745.  
  746. /*****************************************************************************
  747. * Delete one InterSegment PSeg, from InterSegmentList PSegList:             *
  748. *****************************************************************************/
  749. static void DeleteSegInterList(InterSegmentStruct *PSeg,
  750.                         InterSegmentStruct **PSegList)
  751. {
  752.     InterSegmentStruct *PSegTemp;
  753.  
  754.     if (*PSegList == PSeg) { /* Its the first one - simply advance list ptr: */
  755.     *PSegList = (*PSegList) -> Pnext;
  756.     }
  757.     else {
  758.     PSegTemp = (*PSegList);
  759.     while (PSegTemp -> Pnext != NULL && PSegTemp -> Pnext != PSeg)
  760.         PSegTemp = PSegTemp -> Pnext;
  761.     if (PSegTemp -> Pnext == PSeg)
  762.         PSegTemp -> Pnext = PSegTemp -> Pnext -> Pnext;
  763.     else
  764.         IritFatalError("DeleteSegInterList: element to delete not found");
  765.     }
  766. }
  767.  
  768. /*****************************************************************************
  769. * Search for matching point, in the given inter segment list. Returns the    *
  770. * pointer to that element after swapping its points if needed (the match     *
  771. * must be with point 0 of new segment returned), and deleting it from list   *
  772. *****************************************************************************/
  773. static InterSegmentStruct *FindMatchInterList(PointType Pt,
  774.                         InterSegmentStruct **PSegList)
  775. {
  776.     InterSegmentStruct
  777.     *PSegTemp = (*PSegList);
  778.  
  779. #ifdef DEBUG3
  780.     printf("Enter FindMatchInterList\n");
  781. #endif /* DEBUG3 */
  782.  
  783.     while (PSegTemp != NULL) {
  784.     if (PT_APX_EQ(Pt, PSegTemp -> PtSeg[0])) {
  785.         DeleteSegInterList(PSegTemp, PSegList);
  786.         return PSegTemp;
  787.     }
  788.     if (PT_APX_EQ(Pt, PSegTemp -> PtSeg[1])) {
  789.         DeleteSegInterList(PSegTemp, PSegList);
  790.         SwapPointInterList(PSegTemp);
  791.         return PSegTemp;
  792.     }
  793.     PSegTemp = PSegTemp -> Pnext;
  794.     }
  795.  
  796.     IritFatalError("FindMatchInterList: No match found - Empty Object Result");
  797.     return NULL;
  798. }
  799.  
  800. /*****************************************************************************
  801. *   Sort the open loops of the given polygon to an order that can be used in *
  802. * subdividing the polygons later (see comments for ExtractPolygons).         *
  803. *   This order is such that each loops will have no other loop between its   *
  804. * end points, if we walk along the polygon in the (linked list direction)    *
  805. * perimeter from one end to the other, before it. For example:             *
  806. *             -----------------------------L3                 *
  807. *        |  ---------------L1  -----L2 |          --------L4   --L5   *
  808. *        | |               |  |     |  |         |        |   |  |    *
  809. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 *
  810. * In this case, any order such that L1, L2 are before L3 will do. Obviously  *
  811. * this is not a total order, and they are few correct ways to sort it.         *
  812. * Algorithm:                                     *
  813. *   For each open loop, for each of its two end, evaluate a RealType key for *
  814. * the end point P between segment P(i) .. P(i+1) to be i + t, where:         *
  815. * t is the ratio  (P - P(i)) / (P(i+1) - P(i)) . This maps the all perimeter *
  816. * of the polygon onto 0..N-1, where N is number of vertices of that polygon. *
  817. *   Sort the keys, and while they are keys in data sturcture, search and     *
  818. * remove a consecutive pair of keys assosiated with same loop, and output it *
  819. *   Note that each open loop point sequence is tested to be such that it     *
  820. * starts on the first point (first and second along vertex list) on polygon  *
  821. * perimeter, and the sequence end is on the second point, and the sequence   *
  822. * is reversed if not so. This order will make the replacement of the         *
  823. * perimeter from first to second points by the open loop much easier.         *
  824. *   This may be real problem if there are two intersection points almost     *
  825. * identical - floating point errors may cause it to loop forever. We use     *
  826. * some reordering heuristics in this case, and return fatal error if fail!   *
  827. *****************************************************************************/
  828. void SortOpenInterList(IPPolygonStruct *Pl, InterSegListStruct **POpen)
  829. {
  830.     int Found = TRUE,
  831.     ReOrderFirst = FALSE,
  832.     NumOfReOrders = 0;
  833.     RealType Key1, Key2;
  834.     InterSegmentStruct *PSeg;
  835.     InterSegListStruct *PLSeg, *PLNext,
  836.     *PResTemp = NULL,
  837.     *PResHead = NULL;
  838.     SortOpenStruct *PSTemp, *PSTemp1, *PSTemp2,
  839.     *PSHead = NULL;
  840.  
  841. #ifdef DEBUG3
  842.     printf("Enter SortOpenInterList\n");
  843. #endif /* DEBUG3 */
  844.  
  845.     PLSeg = (*POpen);
  846.     while (PLSeg != NULL) {    /* Evaluate the two end keys and insert them: */
  847.         PSeg = PLSeg -> PISeg;
  848.     PLNext = PLSeg -> Pnext;
  849.     PLSeg -> Pnext = NULL;
  850.  
  851.     PSTemp1 = (SortOpenStruct *) IritMalloc(sizeof(SortOpenStruct));
  852.     PSTemp1 -> PLSeg = PLSeg;
  853.     /* Insert PSTemp1 into PLHead list according to position of Pt in Pl.*/
  854.     Key1 = SortOpenInsertOne(&PSHead, PSTemp1, PSeg -> PtSeg[0],
  855.                            PSeg -> V[0], Pl);
  856.  
  857.     while (PSeg -> Pnext != NULL) PSeg = PSeg -> Pnext; /* Go other end. */
  858.     PSTemp2 = (SortOpenStruct *) IritMalloc(sizeof(SortOpenStruct));
  859.     PSTemp2 -> PLSeg = PLSeg;
  860.     /* Insert PSTemp2 into PLHead list according to position of Pt in Pl.*/
  861.     Key2 = SortOpenInsertOne(&PSHead, PSTemp2, PSeg -> PtSeg[1],
  862.                            PSeg -> V[1], Pl);
  863.  
  864.     if (Key1 > Key2)          /* Reverse the open loop points order: */
  865.         SortOpenReverseLoop(PSTemp1);
  866.  
  867.     PLSeg = PLNext;
  868.     }
  869.  
  870.     while (PSHead != NULL) {    /* Search for consecutive pair of same loop. */
  871.     if (NumOfReOrders++ > 10)
  872.         IritFatalError("SortOpenInterList: fail to sort intersection list");
  873.     if (Found)
  874.         NumOfReOrders = 0;
  875.  
  876.     Found = FALSE;
  877.     PSTemp = PSHead;
  878.     if (PSTemp -> PLSeg == PSTemp -> Pnext -> PLSeg) { /* First is pair! */
  879.         if (PResHead == NULL)
  880.         PResHead = PResTemp = PSTemp -> PLSeg;
  881.         else {
  882.         PResTemp -> Pnext = PSTemp -> PLSeg;
  883.         PResTemp = PSTemp -> PLSeg;
  884.         }
  885.         PSHead = PSHead -> Pnext -> Pnext;         /* Skip the first pair. */
  886.         IritFree((VoidPtr) PSTemp -> Pnext);
  887.         IritFree((VoidPtr) PSTemp);
  888.         Found = TRUE;
  889.         continue;
  890.     }
  891.     /* If we are here, first pair is not of same loop - search on: */
  892.     while (PSTemp -> Pnext -> Pnext != NULL) {
  893.         if (PSTemp -> Pnext -> PLSeg == PSTemp -> Pnext -> Pnext -> PLSeg) {
  894.         if (PResHead == NULL)
  895.             PResHead = PResTemp = PSTemp -> Pnext -> PLSeg;
  896.         else {
  897.             PResTemp -> Pnext = PSTemp -> Pnext -> PLSeg;
  898.             PResTemp = PSTemp -> Pnext -> PLSeg;
  899.         }
  900.         PSTemp2 = PSTemp -> Pnext;
  901.         PSTemp -> Pnext = PSTemp -> Pnext -> Pnext -> Pnext;
  902.         IritFree((VoidPtr) PSTemp2 -> Pnext);
  903.         IritFree((VoidPtr) PSTemp2);
  904.         Found = TRUE;
  905.         break;
  906.         }
  907.         PSTemp = PSTemp -> Pnext;
  908.     }
  909.     /* The only way we might found nothing is in floating point round */
  910.     /* off error - two curve ends has almost the same Key...      */
  911.     /* Note, obviously, that there are at list 4 entries in list.     */
  912.     if (!Found) {
  913.         if (!ReOrderFirst &&
  914.         APX_EQ(PSHead -> Pnext -> Key, PSHead -> Key)) {
  915.         ReOrderFirst = TRUE;
  916.         PSTemp1 = PSHead -> Pnext;
  917.         PSHead -> Pnext = PSTemp1 -> Pnext;
  918.         PSTemp1 -> Pnext = PSHead;
  919.         PSHead = PSTemp1;
  920.         continue;
  921.         }
  922.         else
  923.         ReOrderFirst = FALSE;
  924.         PSTemp = PSHead;
  925.         while (PSTemp -> Pnext -> Pnext != NULL) {
  926.         if (APX_EQ(PSTemp -> Pnext -> Key,
  927.                PSTemp -> Pnext -> Pnext -> Key)) {
  928.             PSTemp1 = PSTemp -> Pnext;
  929.             PSTemp2 = PSTemp1 -> Pnext;
  930.             PSTemp1 -> Pnext = PSTemp2 -> Pnext;
  931.             PSTemp2 -> Pnext = PSTemp1;
  932.             PSTemp -> Pnext = PSTemp2;
  933.             break;
  934.         }
  935.         PSTemp = PSTemp -> Pnext;
  936.         }
  937.     }
  938.     }
  939.  
  940.     *POpen = PResHead;
  941.  
  942. #ifdef DEBUG3
  943.     printf("Exit SortOpenInterList\n");
  944. #endif /* DEBUG3 */
  945. }
  946.  
  947. /*****************************************************************************
  948. *   Reverse the order of the open loop pointed by PSHead.             *
  949. *****************************************************************************/
  950. static void SortOpenReverseLoop(SortOpenStruct *PSHead)
  951. {
  952.     InterSegmentStruct *PIHead, *PITemp,
  953.     *PINewHead = NULL;
  954.  
  955.     PIHead = PSHead -> PLSeg -> PISeg;
  956.  
  957.     while (PIHead != NULL) {
  958.     PITemp = PIHead;
  959.     PIHead = PIHead -> Pnext;
  960.     SwapPointInterList(PITemp);
  961.     PITemp -> Pnext = PINewHead;
  962.     PINewHead = PITemp;
  963.     }
  964.  
  965.     PSHead -> PLSeg -> PISeg = PINewHead;
  966. }
  967.  
  968. /*****************************************************************************
  969. *   Insert new loop PSTemp, defines key by Pt and V (V defines the vertex    *
  970. * and P is the points on it), into (decreasing) ordered list PSHead.         *
  971. *****************************************************************************/
  972. static RealType SortOpenInsertOne(SortOpenStruct **PSHead,
  973.                SortOpenStruct *PSTemp, PointType Pt, IPVertexStruct *V,
  974.                               IPPolygonStruct *Pl)
  975. {
  976.     int i = 0;
  977.     RealType Key;
  978.     PointType Pt1, Pt2;
  979.     IPVertexStruct
  980.     *VTemp = Pl -> PVertex;
  981.     SortOpenStruct *PSTail;
  982.  
  983.     PSTemp -> Pnext = NULL;
  984.  
  985.     while (VTemp != V && VTemp != NULL) {
  986.     i++;
  987.     VTemp = VTemp -> Pnext;
  988.     }
  989.     if (VTemp == NULL)
  990.     IritFatalError("SortOpenInsertOne: fail to find vertex");
  991.  
  992.     PT_SUB(Pt1, V -> Pnext -> Coord, V -> Coord);
  993.     PT_SUB(Pt2, Pt, V -> Coord);
  994.     Key = PSTemp -> Key = i + PT_LENGTH(Pt2) / PT_LENGTH(Pt1);
  995.  
  996.     /* Now insert PSTemp into the ordered list: */
  997.     if (*PSHead == NULL) {
  998.     *PSHead = PSTemp;
  999.     return Key;
  1000.     }
  1001.     if (PSTemp -> Key > (*PSHead) -> Key) {         /* Insert as first? */
  1002.     PSTemp -> Pnext = (*PSHead);
  1003.     *PSHead = PSTemp;
  1004.     return Key;
  1005.     }
  1006.     PSTail = (*PSHead);
  1007.     while (PSTail -> Pnext != NULL && PSTemp -> Key < PSTail -> Pnext -> Key)
  1008.     PSTail = PSTail -> Pnext;
  1009.     PSTemp -> Pnext = PSTail -> Pnext;
  1010.     PSTail -> Pnext = PSTemp;
  1011.  
  1012.     return Key;
  1013. }
  1014.  
  1015. #ifdef DEBUG2
  1016.  
  1017. /*****************************************************************************
  1018. *   Print the content of the given polygon, to standard output.             *
  1019. *****************************************************************************/
  1020. static void PrintVrtxList(IPVertexStruct *V)
  1021. {
  1022.     IPVertexStruct
  1023.     *VHead = V;
  1024.  
  1025.     do {
  1026.     printf("    %12lf %12lf %12lf\n",
  1027.            V -> Coord[0], V -> Coord[1], V -> Coord[2]);
  1028.     V = V -> Pnext;
  1029.     }
  1030.     while (V!= NULL && V != VHead);
  1031. }
  1032.  
  1033. /*****************************************************************************
  1034. *   Print the content of the given InterSegment list, to standard output.    *
  1035. *****************************************************************************/
  1036. static void PrintInterList(InterSegmentStruct *PInt)
  1037. {
  1038.     printf("INTER SEGMENT LIST:\n");
  1039.  
  1040.     if (PInt)
  1041.     printf("Entry vertex pointer %p\n", PInt -> V[0]);
  1042.     while (PInt) {
  1043.     printf("%9lg %9lg %9lg (%04x), %9lg %9lg %9lg (%04x)\n",
  1044.         PInt->PtSeg[0][0], PInt->PtSeg[0][1], PInt->PtSeg[0][2],
  1045.         PInt->V[0],
  1046.         PInt->PtSeg[1][0], PInt->PtSeg[1][1], PInt->PtSeg[1][2],
  1047.         PInt->V[1]);
  1048.     if (PInt -> Pnext == NULL)
  1049.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  1050.  
  1051.     PInt = PInt -> Pnext;
  1052.     }
  1053. }
  1054.  
  1055. #endif /* DEBUG2 */
  1056.